// 模拟实现priority_queue - 堆

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;


namespace sl // 防止命名冲突
{
    // 比较方式 - 使内部结构成为大堆
    template<class T>
    struct less
    {
        bool operator()(const T& x, const T& y)
        {
            return x < y;
        }
    };

    // 比较方式 - 使内部结构成为小堆
    template<class T> 
    struct greater
    {
        bool operator()(const T& x, const T& y)
        {
            return x > y;
        }
    };

    // 优先级队列的模拟实现 - 底层结构是数组，逻辑结构是一颗二叉树
    template<class T, class Container = vector<T>, class Compare = less<T>>
    class priority_queue
    {
    private:
        Container _con; // 底层容器
        Compare _comp; // 比较方式

    public:
        // // 堆的向上调整
        // void adjustUp(int child)
        // {
        //     // 通过孩子节点计算父节点
        //     int parent = (child - 1) / 2;

        //     while(child > 0) // 调整到根节点的位置截止
        //     {
        //         if(_comp(_con[parent], _con[child])) // 通过所给的比较方式判断是否需要交换节点
        //         {
        //             // 将父节点与孩子节点进行交换
        //             swap(_con[parent], _con[child]);
        //             // 继续向上进行调整
        //             child = parent;
        //             parent = (child - 1) / 2;
        //         }
        //         else
        //         {
        //             break; // 符合堆的条件，结束循环
        //         }
        //     }
        // }

        // // 堆的向下调整
        // void adjustDown(int n, int parent)
        // {
        //     int child = parent * 2 + 1; // 默认选择的是左孩子

        //     while(child < n) // 调整到叶子节点截止
        //     {
            //     if(child + 1 < n && _comp(_con[child], _con[child + 1]))
        //             child++; // 比较左孩子和右孩子

        //         if(_comp(_con[parent], _con[child]))
        //         {
        //             // 将父节点与孩子节点进行交换
        //             swap(_con[parent], _con[child]);
        //             // 继续向下进行调整
        //             parent = child;
        //             child = parent * 2 + 1;
        //         }
        //         else
        //         {
        //             break; // 符合堆的条件，结束循环
        //         }
        //     }
        // }


        // // 堆的向上调整
        // void adjustUp(int child)
        // {
        //     // 通过孩子节点计算出父节点的值
        //     int parent = (child - 1) / 2;

        //     while(child > 0) // 调整到根节点结束
        //     {
        //         // 比较父节点和孩子节点的值
        //         if(_comp(_con[parent], _con[child]))
        //         {
        //             // 交换父节点和孩子节点
        //             swap(_con[parent], _con[child]);
        //             // 继续向上调整
        //             child = parent;
        //             parent = (child - 1) / 2;
        //         }
        //         else
        //         {
        //             break;
        //         }
        //     }
        // }

        // // 堆的向下调整
        // void adjustDown(int n, int parent)
        // {
        //     // 默认是左孩子节点
        //     int child = parent * 2 + 1;

        //     while(child < n) // 调整到叶子节点结束
        //     {
        //         // 判断左右孩子
        //         if(child + 1 < n && _comp(_con[child], _con[child + 1]))
        //         {
        //             child++;
        //         }

        //         // 比较父节点和孩子节点
        //         if(_comp(_con[parent], _con[child]))
        //         {
        //             swap(_con[parent], _con[child]);
        //             parent = child;
        //             child = parent * 2 + 1;
        //         }
        //         else
        //         {
        //             break;
        //         }
        //     }
        // }

        // // 堆的向上调整
        // void adjustUp(int child)
        // {
        //     // 通过孩子节点计算出父节点
        //     int parent = (child - 1) / 2;

        //     // 调整到根节点结束
        //     while(child > 0)
        //     {
        //         // 比较父节点和孩子节点
        //         if(_comp(_con[parent], _con[child]))
        //         {
        //             // 交换父节点和孩子节点
        //             swap(_con[parent], _con[child]);
        //             // 继续向上进行调整
        //             child = parent;
        //             parent = (child - 1) / 2;
        //         }
        //         else
        //         {
        //             break; // 已成堆
        //         }
        //     }
        // }

        // // 堆的向下调整
        // void adjustDwon(int n, int parent)
        // {
        //     // 通过父节点计算出孩子节点
        //     int child = parent * 2 + 1; // 默认是左孩子

        //     // 调整到叶子节点结束
        //     while(child < n)
        //     {
        //         if(child + 1 < n && _comp(_con[child], _con[child + 1]))
        //         {
        //             child++; // 比较左右孩子
        //         }

        //         // 比较父节点和孩子节点
        //         if(_con[parent], _con[child])
        //         {
        //             swap(_con[parent], _con[child]);
        //             parent = child;
        //             child = parent * 2 + 1;
        //         }
        //         else
        //         {
        //             break;
        //         }
        //     }
        // }

        // 堆的向上调整
        void adjustUp(int child)
        {
            // 根据孩子节点计算父节点
            int parent = (child - 1) / 2;

            while(child > 0) // 调整到根节点结束
            {
                // 比较父节点和孩子节点
                if(_comp(_con[parent], _con[child]))
                {
                    // 交换父节点和孩子节点
                    swap(_comp[parent], _comp[child]);
                    // 继续向上进行调整
                    child = parent;
                    parent = (child - 1) / 2;
                }
                else
                {
                    break; // 已成堆
                }
            }
        }

        // 堆的向下调整
        void adjustDown(int n, int parent)
        {
            // 根据父节点计算孩子节点
            int child = parent * 2 + 1;

            // 调整到叶子节点结束
            while(child > n)
            {
                // 比较左右孩子
                if(child + 1 < n && _comp(_con[child], _con[child + 1]))
                {
                    child++;
                }

                // 比较父节点和孩子节点
                if(_comp(_con[parent], _con[child]))
                {
                    // 交换父节点和孩子节点
                    swap(_con[parent], _con[child]);
                    // 继续向下进行调整
                    parent = child;
                    child = parent * 2 + 1;
                }
                else
                {
                    break;
                }
            }
        }

        // 插入元素到堆尾并排序
        void push(const T& x)
        {
            _con.push_back(x);
            adjustup(_con.size() - 1); // 将最后一个元素进行一次向上调整
        }

        // 弹出堆顶元素
        void pop()
        {
            // 将堆头元素和堆尾元素进行交换
            swap(_con[0], _con[_con.size() - 1]);
            _con.pop_back();
            adjustDown(_con.size(), 0); // 将第0个元素进行一次向下调整
        }

        // 访问堆顶元素
        T& top()
        {
            return _con[0];
        }

        const T& top() const
        {
            return _con[0];
        }

        // 获取堆中有效元素的个数
        int size() const
        {
            return _con.size();
        }

        // 判断堆是否为空
        bool empty() const
        {
            return _con.empty();
        }

    };
}



